package leetCode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    /**
     * 30. 串联所有单词的子串
     * https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/
     * @param s
     * @param words
     * @return
     */
    public List<Integer> findSubstring2(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        Map<String, Integer> map1 = new HashMap<>();
        int len = words[0].length(), size = words.length, m = s.length();//数组字符串长度，数组个数，s的字符串长度
        //把words数组的字符串存进map1中
        for(String str : words) {
            map1.put(str, map1.getOrDefault(str, 0) + 1);
        }
        for(int i = 0; i < len; i++) {
            Map<String, Integer> map2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right + len <= m; right += len) {
                //入窗口
                String in = s.substring(right, right + len);
                map2.put(in, map2.getOrDefault(in, 0) + 1);
                if(map2.get(in) <= map1.getOrDefault(in, 0)) count++;//维护count
                //判断
                if(right - left + 1 > len * size) {
                    //出窗口
                    String out = s.substring(left, left + len);
                    left += len;
                    if(map2.get(out) <= map1.getOrDefault(out, 0)) count--;
                    map2.put(out, map2.get(out) - 1);
                }
                //更新结果
                if(count == size) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }
    //err
    public List<Integer> findSubstring1(String s, String[] words) {
        List<Integer> ret = new ArrayList<>();
        Map<String, Integer> map1 = new HashMap<>();
        Map<String, Integer> map2 = new HashMap<>();
        int len = words[0].length();//统计字符数组里每个字符的个数
        int lenCount = len;//要移动多少次窗口
        int size = words.length;//统计字符数组的个数
        for(String str : words) {
            //把数组存放进map2中
            map2.put(str, map2.getOrDefault(str, 0) + 1);
        }
        //窗口要移动len次
        while(lenCount > 0) {
            for(int left = len - lenCount, right = len - lenCount, count = 0; right < s.length(); ) {
                //进窗口
                String in = getString(s, right, len);
                map1.put(in, map1.getOrDefault(in, 0) + 1);
                right += len;
                //维护count
                if(map1.get(in) <= map2.get(in)) count++;
                //判断
                if((right - left + 1) / len > size) {
                    String out = getString(s, left, len);
                    if(map1.get(out) <= map2.get(out)) count--;
                    //出窗口
                    if(map1.get(out) == 1) {
                        map1.remove(out);
                    } else {
                        map1.put(out, map1.get(out) - 1);
                    }
                    left += len;
                }
                //更新结果
                if(count == size) {
                    ret.add(left);
                }
            }
            map1.clear();
            lenCount--;
        }
        return ret;
    }
    public static String getString(String str, int start, int num) {
        char[] ch = new char[num];
        int count = 0;
        while(num > 0) {
            if(start + count >= str.length()) return null;
            ch[count] = str.charAt(start + count);
            count++;
            num--;
        }
        String ret = new String(ch);
        return ret;
    }
}